#include "utils.h"
#include "intersection_finder.h"
#include <crtdbg.h>

#define IS_LINE_SEGMENTS is_line_segments

#define IS_ORIGINAL(v) (v < 1)

// no_ip case FindInt finds and reports intersection of segment whith staircase QB<stair_index <= QE, given location of the segment begin point - l
void CIntersectionFinder::no_ipFindInt(int QB, int QE, int l, PSeg s)
{
	int c = l;
	while ((c > QB) && (IntersectionsInCurStripe(no_ipQ[c].s, s))) //first get intersections below
		c--;
	if (c != l)
		return; //if found it can't be any more
	c = l + 1;
	while ((c <= QE) && (IntersectionsInCurStripe(no_ipQ[c].s, s))) // get intersections above
		c++;
};

// FindIntL finds and reports intersection of L with current staircase QB<stair_index <= QE for fast algorithm
// locations of the segments should be placed to Loc array before calling the function
void CIntersectionFinder::no_ipFindIntL(int QB, int QE, int segm_numb)
{
	for (int i = 0; i < segm_numb; i++)
	{
		int s_idx = no_ipL[i].s;
		if (SegmentBE[s_idx].E < RBoundIdx) //if segment is not covering the stripe
			no_ipFindInt(QB, QE, Loc[i], Scoll[s_idx]);// find intersections
	}
}

// FindIntI - finds and reports intersections of the segment seg with ancestor staircases (listed in program stack)
// from top of the hierarchy to bottom stopping on last staircase for which seg is internal
void CIntersectionFinder::no_ipFindIntI(int r_index, ProgramStackRec * stack_pos, PSeg seg)
{
	while (stack_pos->right_bound <= r_index)stack_pos = stack_pos->prev;// go from bottom to top and find staircase to start
	E = ENDS[r_index].x;// adjust right bound for segment functions helpers
	int l, r, m, QB, QE = stack_pos->Q_pos; 
	for (stack_pos = stack_pos->prev;stack_pos;stack_pos = stack_pos->prev)
	{
		l = QB = stack_pos->Q_pos; 
		r = QE + 1;
		while ((r - l) > 1)// binary search
		{
			m = (r + l) >> 1;//        m = (r+l)/2;
			if (_Under(Scoll[no_ipQ[m].s], seg))
				l = m;
			else
				r = m;
		}
		no_ipFindInt(QB, QE, l, seg);
		QE = QB; // move staircase bound to parent staircase
	};
}

// InsDel - inserts or deletes segment associated with end_index to/from L
//retuns new L size
int CIntersectionFinder::no_ipInsDel(int end_index, ProgramStackRec * stack_pos, int Size)
{
	int i;
	TSegmEnd *current_end = ENDS + end_index;
	no_ipExchangeLR();  
	if (current_end->islast) // if endpoint - delete
	{
		int sn = no_ipL[Size].s = current_end->s;
		for (i = 0; no_ipL[i].s != sn; i++); 
		//_ASSERTE(i != Size);
		Size--;
		for (; i < Size; i++)
			no_ipL[i] = no_ipL[i + 1];
	}
	else// if startpoint - insert
	{
		PSeg seg = Scoll[current_end->s];
		double X, Y;
		_BegPoint(seg, X, Y);
		for (i = Size - 1;(i > -1) && (no_ipL[i].y >= Y); i--)
			no_ipL[i + 1] = no_ipL[i];
		no_ipL[i + 1].s = current_end->s;
		Size++;

		no_ipFindIntI(SegmentBE[current_end->s].E, stack_pos, seg);// get internal intersections
	}
	return Size;
}

// Merge merges R and current staircase QB<stair_index <= QE on right bound of the stripe and place it in L, 
// than exchange it back to R and returns new R size.  While merging finds locations of R segments
// in current staircase and appropriate intersections.
int CIntersectionFinder::no_ipMerge(int QB, int QE, int Size)
{
	int new_size = 0;
	no_ipSegmentInfo *cur_R_pos = no_ipR, *last_R_pos = no_ipR + Size;
	int cur_stair = QB;
	while ((cur_stair < QE) && (cur_R_pos < last_R_pos))
	{
		if (cur_R_pos->y < no_ipQ[cur_stair + 1].y)
		{
			if (SegmentBE[cur_R_pos->s].B > LBoundIdx)
				no_ipFindInt(QB, QE, cur_stair, Scoll[cur_R_pos->s]);      
			no_ipL[new_size++] = *cur_R_pos;
			cur_R_pos++;
		}
		else
			no_ipL[new_size++] = no_ipQ[++cur_stair];
	}
	while (cur_R_pos < last_R_pos)
	{
		if (SegmentBE[cur_R_pos->s].B > LBoundIdx)
			no_ipFindInt(QB, QE, QE, Scoll[cur_R_pos->s]);      
		no_ipL[new_size++] = *cur_R_pos;
		cur_R_pos++;
	}
	while (cur_stair < QE)
		no_ipL[new_size++] = no_ipQ[++cur_stair];
	no_ipExchangeLR();
	return new_size;
};

// Split - splits L into new staircase and new L, new L temporary placed to R, at the end L and R exchanged.
// While executing finds location of new L segments in new staicase and finds intersection of the new L segments
// covering current strip with the staircase stairs below.   

// same as Split but more fast intersection checking without finding intersection point
int CIntersectionFinder::no_ipSplit(int &step_index, int Size, int stripe_divided)
{
	int father_last_step = step_index, new_L_size = 0;
	no_ipSegmentInfo *cur_L_pos = no_ipL, *last_L_pos = no_ipL + Size;
	for (; cur_L_pos < last_L_pos; cur_L_pos++)
	{
		if (SegmentBE[cur_L_pos->s].E >= RBoundIdx)//segment is covering current stripe
		{
			int step = step_index;
			PSeg ps = Scoll[cur_L_pos->s];
			//  at the left edge of the stripe current segment must have bigger Y coord when all segments of current staircase 
			if (stripe_divided)
				cur_L_pos->y = _YAtX(ps, E); // Y coordinate of current segment at right edge of the stripe
			while ((father_last_step < step) && (no_ipQ[step].y > cur_L_pos->y))// current segment intersects all segments of the staircase having bigger Y coords at the stripe right edge  
			{
				_RegIntersection(_reg_obj, Scoll[no_ipQ[step].s], ps, 1, NULL);
				step--;
			}// intersection point remains unknown, so we register only pair passing NULL as last param to _RegIntersection
			if (step_index != step)
			{
				int_numb += step_index - step;
				no_ipR[new_L_size] = *cur_L_pos;
				Loc[new_L_size++] = step_index;
			}
			else
			{
				step_index++;
				no_ipQ[step_index] = *cur_L_pos;
			}  
		}
		else
		{
			no_ipR[new_L_size].s = cur_L_pos->s;
			Loc[new_L_size++] = step_index;
		}
	}
	no_ipExchangeLR();
	return new_L_size;
};

int CIntersectionFinder::no_ipSearchInStrip(int QP, int Size)
{
	if (!Size)
		return 0;
	if (Size < 2)
	{
		no_ipR->y = _YAtX(Scoll[no_ipR->s = no_ipL->s], E); 
		return 1;
	}
	int NQP = QP;
	int size = Size;
	if (size = no_ipSplit(NQP, size, TRUE))
	{
		no_ipSegmentInfo *q = no_ipQ + QP + 1;
		do
		{
			no_ipFindIntL(QP, NQP, size);
			QP = NQP;
		}
		while (size = no_ipSplit(NQP, size, FALSE));
		// at this point we can just place Q starting from QP+1 to R and sort it
		for (QP = 0; QP < Size; QP++)
			no_ipR[QP] = q[QP];
		fastsort(no_ipR, Size);
	}
	return Size;
}

int CIntersectionFinder::no_ipFindR(int ladder_start_index, int interval_left_index, int interval_right_index, 
									 ProgramStackRec *stack_pos, int Size, int call_numb)
{
	//  int RSize;
	B = ENDS[interval_left_index].x;
	E = ENDS[RBoundIdx = interval_right_index].x; 
	if (interval_right_index - interval_left_index == 1)
		return no_ipSearchInStrip(ladder_start_index, Size);
	ProgramStackRec stack_rec(ladder_start_index);
	int_numb = 0;// variable to count intersections on Split stage
	if (Size > 0)
	{
		Size = no_ipSplit(stack_rec.Q_pos, Size, call_numb ? FALSE : TRUE);
		if (ladder_start_index < stack_rec.Q_pos)
		{
			no_ipFindIntL(ladder_start_index, stack_rec.Q_pos, Size);
			stack_pos = stack_rec.Set(stack_pos, interval_right_index);
		}
	}
	if ((int_numb > Size) && (call_numb < max_call)) //if found a lot of intersections repeat FindR
		Size = no_ipFindR(stack_rec.Q_pos, interval_left_index, interval_right_index, stack_pos, Size, call_numb+1);
	else //cut stripe on the middle
	{
		int m = (interval_left_index + interval_right_index) / 2; 
		Size = no_ipFindR(stack_rec.Q_pos, interval_left_index, m, stack_pos, Size, 0);
		Size = no_ipInsDel(m, stack_pos, Size);
		Size = no_ipFindR(stack_rec.Q_pos, m, interval_right_index, stack_pos, Size, 0);
	}
	if (ladder_start_index >= stack_rec.Q_pos) return Size;
	B = ENDS[LBoundIdx = interval_left_index].x;
	E = ENDS[interval_right_index].x;
	Size = no_ipMerge(ladder_start_index, stack_rec.Q_pos, Size);
	return Size;
};

void CIntersectionFinder::FreeMem()
{
#define MY_FREE_ARR_MACRO(a) if (a) {delete[] a; a = NULL;}
	MY_FREE_ARR_MACRO(Q);
	MY_FREE_ARR_MACRO(SegmentBE);
	MY_FREE_ARR_MACRO(L);
	MY_FREE_ARR_MACRO(R);
	MY_FREE_ARR_MACRO(ENDS);
	MY_FREE_ARR_MACRO(Loc);
	MY_FREE_ARR_MACRO(no_ipL);
	MY_FREE_ARR_MACRO(no_ipR);
	MY_FREE_ARR_MACRO(no_ipQ);
};

void CIntersectionFinder::no_ipAllocMem()
{
	SegmentBE = new EndIndexes[nTotSegm];
	no_ipL = new no_ipSegmentInfo[nTotSegm + 1];
	no_ipR = new no_ipSegmentInfo[nTotSegm + 1];
	ENDS = new TSegmEnd[2 * nTotSegm];
	Loc = new int[nTotSegm];
	no_ipQ = new no_ipSegmentInfo[nTotSegm];
};

int CIntersectionFinder::prepare_ends(int n)
{
	int i, j;
	double y;
	for (i = 0, j = 0; i < n; i++)
	{
		ENDS[j].s = i;
		_BegPoint(Scoll[i], ENDS[j].x, y);
		ENDS[j].islast = 0;
		j++;
		_EndPoint(Scoll[i], ENDS[j].x, y);
		ENDS[j].s = i;
		ENDS[j].islast = 1;
		j++;
	}
	fastsort(ENDS, j);
	for (int i = 0; i < 2 * n; i++)
		if (ENDS[i].islast)
			SegmentBE[ENDS[i].s].E = i;
		else
			SegmentBE[ENDS[i].s].B = i;

	if (ENDS[0].s == ENDS[2 * n - 1].s)
	{
		PSeg s = Scoll[ENDS[0].s];
		for (int i = 0; i < n; i++)
			if (s != Scoll[i])
				_FindAndRegIPoints(s, Scoll[i], _reg_obj, dont_need_int_points);
		return 0;
	}
	if (no_ipL)
		no_ipL[0].s = ENDS[0].s;
	else  
		L[0] = ENDS[0].s; 
	return 1;

};

CIntersectionFinder::CIntersectionFinder()
{
	SegmentBE = NULL;
	_reg_obj = NULL;
	Q = NULL;
	L = NULL;
	R = NULL;
	ENDS = NULL;
	Scoll = NULL;
	Loc = NULL;
	dont_need_int_points = FALSE;
	no_ipL = NULL;
	no_ipR = NULL;
	no_ipQ = NULL;
	memset(my_counter, 0, sizeof(my_counter));
};

void CIntersectionFinder::set_segm_fuctions(
	FBelow below, 
	FFindAndRegIPoints findAndRegIPoints, 
	FFindAndRegIPointsInStripe findAndRegIPointsInStripe,
	FGetPoint begPoint, 
	FGetPoint endPoint, 
	FUnder under, 
	FYAtX yAtX, 
	FRegIntersection regIntersection, 
	PRegObj reg_obj, 
	int is_line
	)
{
	_Below = below;
	_FindAndRegIPoints = findAndRegIPoints;
	_FindAndRegIPointsInStripe = findAndRegIPointsInStripe;
	_BegPoint = begPoint;
	_EndPoint = endPoint;
	_Under = under;
	_YAtX = yAtX;
	_RegIntersection = regIntersection;
	_reg_obj = reg_obj;
	is_line_segments = is_line;
}

void CIntersectionFinder::balaban_no_ip(int n, PSeg _Scoll[])
{
	Scoll = _Scoll;
	nTotSegm = n;
	no_ipAllocMem();

	int Size = prepare_ends(n);
	ProgramStackRec stack_rec(-1, 2 * n);  //need to be initialized this way
	Size = no_ipFindR(-1, 0,  n  , &stack_rec, Size, 0);
	Size = no_ipInsDel(n, &stack_rec, Size);
	Size = no_ipFindR(-1, n, 2*n - 1, &stack_rec, Size, 0);

	FreeMem();
}